//describe:Enter a unsorted array, find one of the biggest subarray of subarray, returns to its maximum value
//ex:input array[-1,2,3,-3,4]
//   return 6       ----->[2,3,-3,4]

#include<stdio.h>

int Max(int a, int b)
{
	return a > b ? a : b;
}

int Maximum(int arr[], size_t len)
{
	int start = arr[0];
	int max = arr[0];
	for (int i = 1; i < len; i++)
	{
		start = Max(arr[i], arr[i] + start);
		max = Max(start, max);
	}
	return max;
}

int main()
{
	int arr[] = { -1, 2, 3, -3, 4 };
	int ret = Maximum(arr, sizeof(arr) / 4);
	printf("%d\n", ret);
	return 0;
}
//describe:Knapsack problem
//Is one of the biggest can put 10 kg backpack, there are five items, each are not identical,
//their value and weight can ask what is the maximum value in the backpack
//         input arr_value [5,9,2,4,10]
//               arr_weight[4,3,5,7,6]

#include<stdio.h>

#define MAX_NUM 5
#define MAX_WEIGHT 10
int Max(int a, int b)
{
	return a > b ? a : b;
}


int Maximum(int v[], int v_len, int w[], int w_len, int max[][MAX_WEIGHT])
{
	
	for (int i = 0; i < v_len; i++)
	{
		for (int j = 0; j < w_len; j++)
		{
			max[i][j] = 0;
		}
	}
	for (int i = 0; i < v_len; i++)
	{
		for (int j = 1; j <w_len; j++)
		{
			if (i >= 1)
			{
				if (w[i]>j)
				{
					max[i][j] = max[i - 1][j];
				}
				else
				{
					max[i][j] = Max(max[i - 1][j], max[i - 1][j - w[i]] + v[i]);
				}
			}
			else
			{
				if (w[i] < j)
				{
					max[i][j] = v[i];
				}
				else
				{
					max[i][j] = 0;
				}
			}
		}
	}
	return max[4][9];
}


int main()
{
	int v[] = { 5, 9, 2, 4, 10 };
	int w[] = { 4, 3, 5, 7, 6 };
	int max[MAX_NUM][MAX_WEIGHT];
	int ret = Maximum(v, MAX_NUM, w, MAX_WEIGHT, max);
	printf("%d\n", ret);
	return 0;
}